package com.fw.leetcode.dynamicprogram;

import com.fw.leetcode.LeetCode;

import java.util.List;

/**
 * 198. House Robber
 * 打家劫舍 房间偷钱最大化
 *
 * You are a professional robber planning to rob houses along a street.
 * Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them
 * is that adjacent houses have security systems connected and it will automatically contact the police if two
 * adjacent houses were broken into on the same night.
 *
 * Given an integer array nums representing the amount of money of each house, return the maximum amount of money
 * you can rob tonight without alerting the police.
 *
 * Example 1:
 *  Input: nums = [1,2,3,1]
 *  Output: 4
 *  Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
 *               Total amount you can rob = 1 + 3 = 4.
 *
 * Example 2:
 *  Input: nums = [2,7,9,3,1]
 *  Output: 12
 *  Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
 *               Total amount you can rob = 2 + 9 + 1 = 12.
 *
 * Constraints:
 *  1 <= nums.length <= 100
 *  0 <= nums[i] <= 400
 */
public class Num_0198 implements LeetCode {
    private interface Solution {
        int rob(int[] nums);

        default void assertExpected(int[] nums, int expected) {
            if (rob(nums) != expected) {
                rob(nums);
            }
        }
    }

    private static class DpRollArraySolution implements Solution {

        @Override
        public int rob(int[] nums) { // 动态规划（滚动数组）：时O(n) 空O(1)
            /*
             * 房间偷东西（不能偷相邻的两个房间，会触发报警）
             *
             * 从前往后偷
             * f([0,n-1]) = max { [0] + f([2,n-1]), [1] + f([3,n-1]) }
             * 替换0为i，以适配公式
             * f([i,n-1]) = max { [i] + f([i+2,n-1]), [i+1] + f([i+3,n-1]) }
             * 等效转换
             * f[i] = max { nums[i] + f[i+2], nums[i+1] + f[i+3] }
             * f[i-3] = max { nums[i-3] + f[i-1], nums[i-2] + f[i] }
             *
             * f[n] = 0 辅助位
             * f[n-1] = nums[n-1] 仅1个元素
             * f[n-2] = max { nums[n-2], nums[n-1] } 仅2个元素
             * f[n-3] = max { nums[n-3] + f[n-1], nums[n-2] + f[n] } 仅3个元素
             *
             * 从后往前遍历依次迭代至最终结果 f([0,n-1])
             */
            int n = nums.length;
            int result0 = nums[n-1];
            int result1 = result0; // 辅助位，弥补 0 2 3 之间的间隔
            int result2 = 0;
            int result3 = 0;
            if (n == 1) {
                return result0;
            }
            for (int i = n-2; i >= 0; i--) {
                result0 = Math.max(nums[i] + result2, nums[i+1] + result3);
                result3 = result2;
                result2 = result1;
                result1 = result0;
            }
            return result0;
        }
    }

    private static class DpSolution implements Solution {

        @Override
        public int rob(int[] nums) { // 动态规划：时O(n) 空O(n)
            /*
             * 房间偷东西（不能偷相邻的两个房间，会触发报警）
             *
             * 从前往后偷
             * f([0,n-1]) = max { [0] + f([2,n-1]), [1] + f([3,n-1]) }
             * 替换0为i，以适配公式
             * f([i,n-1]) = max { [i] + f([i+2,n-1]), [i+1] + f([i+3,n-1]) }
             * 等效转换
             * f[i] = max { nums[i] + f[i+2], nums[i+1] + f[i+3] }
             * f[i-3] = max { nums[i-3] + f[i-1], nums[i-2] + f[i] }
             * f[i] 代表：后i个房间偷取的最大金额
             *
             * f[n] = 0 辅助位
             * f[n-1] = nums[n-1] 仅1个元素
             * f[n-2] = max { nums[n-2], nums[n-1] } 仅2个元素
             * f[n-3] = max { nums[n-3] + f[n-1], nums[n-2] + f[n] } 仅3个元素
             *
             * 从后往前遍历依次迭代至最终结果 f([0,n-1])
             */
            int n = nums.length;
            int[] result = new int[n+1];
            result[n] = 0;
            result[n-1] = nums[n-1];
            if (n == 1) {
                return result[0];
            }
            result[n-2] = Math.max(nums[n-2], nums[n-1]);
            if (n == 2) {
                return result[0];
            }
            for (int i = n-3; i >= 0; i--) {
                result[i] = Math.max(nums[i] + result[i+2], nums[i+1] + result[i+3]);
            }
            return result[0];
        }
    }

    private static class DpAnotherSolution implements Solution {

        @Override
        public int rob(int[] nums) { // 动态规划（公式简化）：时O(n) 空O(n)
            /*
             * 房间偷东西（不能偷相邻的两个房间，会触发报警）
             *
             * 从前往后偷
             * f([0,n-1]) = max { [0] + f([2,n-1]), [1] + f([3,n-1]) }
             * 简化公式
             * f([0,n-1]) = max { [0] + f([2,n-1]), f([1,n-1]) }
             * 替换0为i，以适配公式
             * f([i,n-1]) = max { [i] + f([i+2,n-1]), f([i+1,n-1]) }
             * 等效转换
             * f[i] = max { nums[i] + f[i+2], f[i+1] }
             * f[i-2] = max { nums[i-2] + f[i], f[i-1] }
             * f[i] 代表：后i个房间偷取的最大金额
             *
             * f[n] = 0 辅助位
             * f[n-1] = nums[n-1] 仅1个元素
             * f[n-2] = max { nums[n-2] + f[n], f[n-1] } 仅2个元素
             *
             * 从后往前遍历依次迭代至最终结果 f([0,n-1])
             */
            int n = nums.length;
            int[] result = new int[n+1];
            result[n] = 0;
            result[n-1] = nums[n-1];
            if (n == 1) {
                return result[0];
            }
            for (int i = n-2; i >= 0; i--) {
                result[i] = Math.max(nums[i] + result[i+2], result[i+1]);
            }
            return result[0];
        }
    }

    private static class DpAnotherRollArraySolution implements Solution {

        @Override
        public int rob(int[] nums) { // 最优：动态规划（公式简化，滚动数组）：时O(n) 空O(1)
            /*
             * 房间偷东西（不能偷相邻的两个房间，会触发报警）
             *
             * 从前往后偷
             * f([0,n-1]) = max { [0] + f([2,n-1]), [1] + f([3,n-1]) }
             * 简化公式
             * f([0,n-1]) = max { [0] + f([2,n-1]), f([1,n-1]) }
             * 替换0为i，以适配公式
             * f([i,n-1]) = max { [i] + f([i+2,n-1]), f([i+1,n-1]) }
             * 等效转换
             * f[i] = max { nums[i] + f[i+2], f[i+1] }
             * f[i-2] = max { nums[i-2] + f[i], f[i-1] }
             * f[i] 代表：后i个房间偷取的最大金额
             *
             * f[n] = 0 辅助位
             * f[n-1] = nums[n-1] 仅1个元素
             * f[n-2] = max { nums[n-2] + f[n], f[n-1] } 仅2个元素
             *
             * 从后往前遍历依次迭代至最终结果 f([0,n-1])
             */
            int n = nums.length;
            int result0 = nums[n-1];
            int result1 = result0;
            int result2 = 0;
            if (n == 1) {
                return result0;
            }
            for (int i = n-2; i >= 0; i--) {
                result0 = Math.max(nums[i] + result2, result1);
                result2 = result1;
                result1 = result0;
            }
            return result0;
        }
    }

    public static void main(String[] args) {
        Solution solution = new DpAnotherRollArraySolution();
        solution.assertExpected(new int[]{1,2,3,1}, 4);
        solution.assertExpected(new int[]{2,7,9,3,1}, 12);
    }
}
